在图论领域中，一个 树 是秩序的建筑化体现。与可能存在多条路径通向同一目的地的混乱网络不同，树为任意两点之间提供了唯一且确定的路径。这种结构约束并非限制，而是层级系统的基础——从希腊诸神的祖先谱系到现代操作系统的目录结构。
1. 树的结构解析
在层级关系出现之前，我们有 自由树。它的定义简洁而优雅：
定义 9.1.1
一个（自由）树 $T$ 是一个简单图，其中对于任意两个顶点 $v$ 和 $w$，存在一条 唯一的简单路径 从 $v$ 到 $w$。这意味着该图既是 连通的 也是 无环的 （无环）。
当我们指定一个特定顶点作为“起点”时，就形成了一个 根树。这一转换引入了空间方向性，关系由其与根节点的距离和方向决定。
层级术语表
在一个以 $v_0$ 为根的树中，考虑一条简单路径 $(v_0, v_1, \dots, v_n)$：
- 父节点： $v_{n-1}$ 是 $v_n$ 的父节点。
- 子节点： $v_n$ 是 $v_{n-1}$ 的子节点。
- 兄弟节点： 拥有相同父节点的顶点。
- 祖先： 从根到 $v_n$ 的路径上的所有顶点（在某些情况下不包括 $v_n$ 本身）。
- 后代： 以 $v$ 为祖先的所有顶点。
结构度量
- 层级： 从根到某个顶点的唯一路径的长度。根节点本身位于 第 0 层。
- 高度： 树中最高的层级编号。
- 叶节点（终端顶点）： 没有子节点的顶点——分支的末端。
- 内部（分支）顶点： 至少有一个子节点的顶点。
🎯 核心概念：子树
一个 子树 是树的一个子集，由某个顶点及其所有后代组成。在文件系统中，这相当于一个文件夹及其内部的所有文件/子文件夹。在图 9.2.1 中， 克洛诺斯 （宙斯、波塞冬、哈迪斯、阿瑞斯）是 乌拉诺斯。
2. 现实世界中的应用
树不仅仅是数学抽象。它们是组织结构的基石：
- 计算机文件系统： 'C:' 盘符是根节点；文件夹是内部顶点；文件是叶节点。
- 行政架构图： CEO 是根节点；经理是内部节点；普通员工是叶节点。
- 决策框架： 解决类似 即时疯狂 或分析 n维立方体平面性 通常涉及在类似树的状态空间中进行导航。